package leetcode.code1466;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
	public int minReorder(int n, int[][] connections) {
		List<Integer>[] ins = new ArrayList[n];
		List<Integer>[] outs = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			ins[i] = new ArrayList<>();
			outs[i] = new ArrayList<>();
		}
		for (int i = 0; i < connections.length; i++) {
			int[] connection = connections[i];
			int a = connection[0], b = connection[1];
			ins[b].add(a);
			outs[a].add(b);
		}
		boolean[] been = new boolean[n];
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		been[0] = true;
		int ans = 0;
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			List<Integer> in = ins[cur];
			for (int i : in) {
				if (!been[i]) {
					been[i] = true;
					queue.add(i);
				}
			}
			List<Integer> out = outs[cur];
			for (int o : out) {
				if (!been[o]) {
					been[o] = true;
					queue.add(o);
					ans++;
				}
			}
		}
		return ans;
	}
}
